From 54c10cf2d8477d142c11129a8d13e6d314ae9658 Mon Sep 17 00:00:00 2001 From: tsteven4 <13596209+tsteven4@users.noreply.github.com> Date: Sat, 5 Aug 2023 09:57:33 -0600 Subject: [PATCH] Introduce efficient member functions for deleting waypoints (#1151) * Introduce efficient member functions for deleting waypoints New functions with complexity O(n) for deleting pre-marked waypoints are: WaypointList::del_wpts RouteList::del_wpts del_wpts route_del_wpts track_del_wpts Use those functions instead of the inefficient versions WaypointList::waypt_del RouteList::del_wpt waypt_del route_del_wpt track_del_wpt. When these functions are using while looping over a waypoint list the overall complexity is O(n^2). This is because these functions themselves amortize to O(n). * review nits. * tweak deletes * use dedicated wpt deletion flag. --- arcdist.cc | 13 ++-- arcdist.h | 28 +++++---- defs.h | 9 ++- discard.cc | 70 ++++++++------------- discard.h | 11 ++-- duplicate.cc | 18 +----- polygon.cc | 17 +++--- polygon.h | 20 +++--- position.cc | 168 ++++++++++++++++++--------------------------------- position.h | 48 ++++++++------- radius.cc | 25 +++----- radius.h | 29 ++++++--- route.cc | 37 ++++++++++++ smplrout.cc | 48 +++++---------- smplrout.h | 5 +- waypt.cc | 22 +++++++ 16 files changed, 277 insertions(+), 291 deletions(-) diff --git a/arcdist.cc b/arcdist.cc index 483076e95..55a33c887 100644 --- a/arcdist.cc +++ b/arcdist.cc @@ -19,6 +19,8 @@ */ +#include "arcdist.h" + #include // for round #include // for printf, sscanf #include // for strtod @@ -28,7 +30,6 @@ #include // for foreach, qPrintable, qint64 #include "defs.h" -#include "arcdist.h" #include "grtcirc.h" // for RAD, gcdist, linedistprj, radtomi #include "src/core/datetime.h" // for DateTime #include "src/core/logging.h" // for Fatal @@ -163,12 +164,11 @@ void ArcDistanceFilter::process() unsigned removed = 0; foreach (Waypoint* wp, *global_waypoint_list) { - auto* ed = (extra_data*) wp->extra_data; - wp->extra_data = nullptr; - if (ed) { + if (wp->extra_data) { + auto* ed = (extra_data*) wp->extra_data; + wp->extra_data = nullptr; if ((ed->distance >= pos_dist) == (exclopt == nullptr)) { - waypt_del(wp); - delete wp; + wp->wpt_flags.marked_for_deletion = 1; removed++; } else if (projectopt) { wp->longitude = ed->prjlongitude; @@ -208,6 +208,7 @@ void ArcDistanceFilter::process() delete ed; } } + del_marked_wpts(); if (global_opts.verbose_status > 0) { printf(MYNAME "-arc: %u waypoint(s) removed.\n", removed); } diff --git a/arcdist.h b/arcdist.h index 6c9d982f2..842fb12f4 100644 --- a/arcdist.h +++ b/arcdist.h @@ -40,14 +40,7 @@ public: void process() override; private: - double pos_dist{}; - char* distopt = nullptr; - char* arcfileopt = nullptr; - char* rteopt = nullptr; - char* trkopt = nullptr; - char* exclopt = nullptr; - char* ptsopt = nullptr; - char* projectopt = nullptr; + /* Types */ struct extra_data { double distance; @@ -58,6 +51,22 @@ private: const Waypoint* arcpt2; }; + /* Member Functions */ + + void arcdist_arc_disp_wpt_cb(const Waypoint* arcpt2); + void arcdist_arc_disp_hdr_cb(const route_head*); + + /* Data Members */ + + double pos_dist{}; + char* distopt = nullptr; + char* arcfileopt = nullptr; + char* rteopt = nullptr; + char* trkopt = nullptr; + char* exclopt = nullptr; + char* ptsopt = nullptr; + char* projectopt = nullptr; + QVector args = { { "file", &arcfileopt, "File containing vertices of arc", @@ -89,9 +98,6 @@ private: }, }; - void arcdist_arc_disp_wpt_cb(const Waypoint* arcpt2); - void arcdist_arc_disp_hdr_cb(const route_head*); - }; #endif // FILTERS_ENABLED #endif // ARCDIST_H_INCLUDED_ diff --git a/defs.h b/defs.h index d53135a10..d5b2c47e9 100644 --- a/defs.h +++ b/defs.h @@ -251,11 +251,13 @@ public: shortname_is_synthetic(0), fmt_use(0), is_split(0), - new_trkseg(0) {} + new_trkseg(0), + marked_for_deletion(0) {} unsigned int shortname_is_synthetic:1; unsigned int fmt_use:2; /* lightweight "extra data" */ unsigned int is_split:1; /* the waypoint represents a split */ unsigned int new_trkseg:1; /* True if first in new trkseg. */ + unsigned int marked_for_deletion:1; /* True if schedulded for deletion. */ }; // These are dicey as they're collected on read. Subsequent filters may change @@ -479,6 +481,7 @@ public: // FIXME: Generally it is inefficient to use an element pointer or reference to define the element to be deleted, use iterator instead, // and/or implement pop_back() a.k.a. removeLast(), and/or pop_front() a.k.a. removeFirst(). void waypt_del(Waypoint* wpt); // a.k.a. erase() + void del_marked_wpts(); // FIXME: Generally it is inefficient to use an element pointer or reference to define the element to be deleted, use iterator instead, // and/or implement pop_back() a.k.a. removeLast(), and/or pop_front() a.k.a. removeFirst(). void del_rte_waypt(Waypoint* wpt); @@ -521,6 +524,7 @@ void waypt_init(); //void update_common_traits(const Waypoint* wpt); void waypt_add(Waypoint* wpt); void waypt_del(Waypoint* wpt); +void del_marked_wpts(); unsigned int waypt_count(); void waypt_status_disp(int total_ct, int myct); //void waypt_disp_all(waypt_cb); /* template */ @@ -658,6 +662,7 @@ public: void add_wpt(route_head* rte, Waypoint* wpt, bool synth, QStringView namepart, int number_digits); // FIXME: Generally it is inefficient to use an element pointer or reference to define the insertion point, use iterator instead. void del_wpt(route_head* rte, Waypoint* wpt); + void del_marked_wpts(route_head* rte); void common_disp_session(const session_t* se, route_hdr rh, route_trl rt, waypt_cb wc); void flush(); // a.k.a. clear() void copy(RouteList** dst) const; @@ -718,6 +723,8 @@ void route_add_wpt(route_head* rte, Waypoint* wpt, QStringView namepart = u"RPT" void track_add_wpt(route_head* rte, Waypoint* wpt, QStringView namepart = u"RPT", int number_digits = 3); void route_del_wpt(route_head* rte, Waypoint* wpt); void track_del_wpt(route_head* rte, Waypoint* wpt); +void route_del_marked_wpts(route_head* rte); +void track_del_marked_wpts(route_head* rte); void route_swap_wpts(route_head* rte, WaypointList& other); void track_swap_wpts(route_head* rte, WaypointList& other); //void route_disp(const route_head* rte, waypt_cb); /* template */ diff --git a/discard.cc b/discard.cc index 249d66a01..47fecbdf6 100644 --- a/discard.cc +++ b/discard.cc @@ -26,7 +26,7 @@ #include // for strtod -#include "defs.h" // for Waypoint, fatal, route_del_wpt, route_disp_all, track_del_wpt, track_disp_all, waypt_del, waypt_disp_all, route_head, rtedata, trkdata, wptdata, fix_none, fix_unknown +#include "defs.h" // for Waypoint, fatal, route_head (ptr only), xstrtoi, del_marked_wpts, route_del_marked_wpts, route_disp_all, track_del_marked_wpts, track_disp_all, waypt_disp_all, fix_none, fix_unknown #include "src/core/logging.h" // for FatalMsg @@ -41,12 +41,10 @@ void DiscardFilter::fix_process_wpt(const Waypoint* wpt) bool delh = false; bool delv = false; - auto* waypointp = const_cast(wpt); - - if ((hdopf >= 0.0) && (waypointp->hdop > hdopf)) { + if ((hdopf >= 0.0) && (wpt->hdop > hdopf)) { delh = true; } - if ((vdopf >= 0.0) && (waypointp->vdop > vdopf)) { + if ((vdopf >= 0.0) && (wpt->vdop > vdopf)) { delv = true; } @@ -56,81 +54,65 @@ void DiscardFilter::fix_process_wpt(const Waypoint* wpt) del = delh || delv; } - if ((satpf >= 0) && (waypointp->sat < satpf)) { + if ((satpf >= 0) && (wpt->sat < satpf)) { del = true; } - if ((fixnoneopt) && (waypointp->fix == fix_none)) { + if ((fixnoneopt) && (wpt->fix == fix_none)) { del = true; } - if ((fixunknownopt) && (waypointp->fix == fix_unknown)) { + if ((fixunknownopt) && (wpt->fix == fix_unknown)) { del = true; } - if ((eleminopt) && (waypointp->altitude < eleminpf)) { + if ((eleminopt) && (wpt->altitude < eleminpf)) { del = true; } - if ((elemaxopt) && (waypointp->altitude > elemaxpf)) { + if ((elemaxopt) && (wpt->altitude > elemaxpf)) { del = true; } - if (nameopt && name_regex.match(waypointp->shortname).hasMatch()) { + if (nameopt && name_regex.match(wpt->shortname).hasMatch()) { del = true; } - if (descopt && desc_regex.match(waypointp->description).hasMatch()) { + if (descopt && desc_regex.match(wpt->description).hasMatch()) { del = true; } - if (cmtopt && cmt_regex.match(waypointp->notes).hasMatch()) { + if (cmtopt && cmt_regex.match(wpt->notes).hasMatch()) { del = true; } - if (iconopt && icon_regex.match(waypointp->icon_descr).hasMatch()) { + if (iconopt && icon_regex.match(wpt->icon_descr).hasMatch()) { del = true; } if (del) { - switch (what) { - case wptdata: - waypt_del(waypointp); - delete waypointp; - break; - case trkdata: - track_del_wpt(head, waypointp); - delete waypointp; - break; - case rtedata: - route_del_wpt(head, waypointp); - delete waypointp; - break; - default: - return; - } + const_cast(wpt)->wpt_flags.marked_for_deletion = 1; } } -void DiscardFilter::fix_process_head(const route_head* trk) -{ - head = const_cast(trk); -} - void DiscardFilter::process() { - WayptFunctor fix_process_wpt_f(this, &DiscardFilter::fix_process_wpt); - RteHdFunctor fix_process_head_f(this, &DiscardFilter::fix_process_head); + auto waypoint_cb_lambda = [this](const Waypoint* wpt) -> void { + fix_process_wpt(wpt); + }; // Filter waypoints. - what = wptdata; - waypt_disp_all(fix_process_wpt_f); + waypt_disp_all(waypoint_cb_lambda); + del_marked_wpts(); // Filter tracks - what = trkdata; - track_disp_all(fix_process_head_f, nullptr, fix_process_wpt_f); + auto track_tlr_lambda = [](const route_head* rte)->void { + track_del_marked_wpts(const_cast(rte)); + }; + track_disp_all(nullptr, track_tlr_lambda, waypoint_cb_lambda); // And routes - what = rtedata; - route_disp_all(fix_process_head_f, nullptr, fix_process_wpt_f); - + auto route_tlr_lambda = [](const route_head* rte)->void { + route_del_marked_wpts(const_cast(rte)); + }; + route_disp_all(nullptr, route_tlr_lambda, waypoint_cb_lambda); } QRegularExpression DiscardFilter::generateRegExp(const QString& glob_pattern) diff --git a/discard.h b/discard.h index ad5c4cfbf..ac0a381db 100644 --- a/discard.h +++ b/discard.h @@ -41,9 +41,13 @@ public: void process() override; private: + /* Member Functions */ + + void fix_process_wpt(const Waypoint* wpt); static QRegularExpression generateRegExp(const QString& glob_pattern); -private: + /* Data Members */ + char* hdopopt = nullptr; char* vdopopt = nullptr; char* andopt = nullptr; @@ -66,8 +70,6 @@ private: int satpf{}; int eleminpf{}; int elemaxpf{}; - gpsdata_type what{}; - route_head* head{}; QVector args = { { @@ -124,9 +126,6 @@ private: }, }; - void fix_process_wpt(const Waypoint* wpt); - void fix_process_head(const route_head* trk); - }; #endif diff --git a/duplicate.cc b/duplicate.cc index fb471154c..4739ae450 100644 --- a/duplicate.cc +++ b/duplicate.cc @@ -77,8 +77,6 @@ void DuplicateFilter::init() void DuplicateFilter::process() { - int delete_flag; // &delete_flag != nullptr - auto wptlist = *global_waypoint_list; auto compare_lambda = [](const Waypoint* wa, const Waypoint* wb)->bool { @@ -88,7 +86,6 @@ void DuplicateFilter::process() QMultiHash wpthash; for (Waypoint* waypointp : wptlist) { - waypointp->extra_data = nullptr; QString key; if (lcopt) { @@ -121,23 +118,12 @@ void DuplicateFilter::process() for (auto it = values.cbegin(); it != values.cend(); ++it) { Waypoint* wpt = *it; if (purge_duplicates || (wpt != wptfirst)) { - wpt->extra_data = &delete_flag; + wpt->wpt_flags.marked_for_deletion = 1;; } } } } - - // For lineary complexity build a new list from the points we keep. - WaypointList oldlist; - waypt_swap(oldlist); - - for (Waypoint* wpt : qAsConst(oldlist)) { - if (wpt->extra_data == nullptr) { - waypt_add(wpt); - } else { - delete wpt; - } - } + del_marked_wpts(); } #endif diff --git a/polygon.cc b/polygon.cc index 002f856a9..7f988ebdb 100644 --- a/polygon.cc +++ b/polygon.cc @@ -19,13 +19,14 @@ */ +#include "polygon.h" + #include // for sscanf #include // for QString #include // for foreach #include "defs.h" -#include "polygon.h" #include "src/core/textstream.h" // for TextStream @@ -257,7 +258,7 @@ void PolygonFilter::process() if (waypointp->extra_data) { ed = (extra_data*) waypointp->extra_data; } else { - ed = (extra_data*) xcalloc(1, sizeof(*ed)); + ed = new extra_data; ed->state = OUTSIDE; ed->override = 0; waypointp->extra_data = ed; @@ -298,19 +299,19 @@ void PolygonFilter::process() stream.close(); foreach (Waypoint* wp, *global_waypoint_list) { - ed = (extra_data*) wp->extra_data; - wp->extra_data = nullptr; - if (ed) { + if (wp->extra_data) { + ed = (extra_data*) wp->extra_data; + wp->extra_data = nullptr; if (ed->override) { ed->state = INSIDE; } if (((ed->state & INSIDE) == OUTSIDE) == (exclopt == nullptr)) { - waypt_del(wp); - delete wp; + wp->wpt_flags.marked_for_deletion = 1; } - xfree(ed); + delete ed; } } + del_marked_wpts(); } #endif // FILTERS_ENABLED diff --git a/polygon.h b/polygon.h index 8849c1b96..4c6d1d179 100644 --- a/polygon.h +++ b/polygon.h @@ -39,14 +39,25 @@ public: void process() override; private: - char* polyfileopt = nullptr; - char* exclopt = nullptr; + /* Types */ struct extra_data { unsigned short state; unsigned short override; }; + /* Member Functions */ + + static void polytest(double lat1, double lon1, + double lat2, double lon2, + double wlat, double wlon, + unsigned short* state, int first, int last); + + /* Data Members */ + + char* polyfileopt = nullptr; + char* exclopt = nullptr; + QVector args = { { "file", &polyfileopt, "File containing vertices of polygon", @@ -58,11 +69,6 @@ private: }, }; - static void polytest(double lat1, double lon1, - double lat2, double lon2, - double wlat, double wlon, - unsigned short* state, int first, int last); - }; #endif // FILTERS_ENABLED #endif // POLYGON_H_INCLUDED_ diff --git a/position.cc b/position.cc index b99f55de3..e4d642d96 100644 --- a/position.cc +++ b/position.cc @@ -28,137 +28,87 @@ #include // for qAsConst, qRound64, qint64 #include "defs.h" -#include "grtcirc.h" // for RAD, gcdist, radtometers #include "src/core/datetime.h" // for DateTime #if FILTERS_ENABLED -double PositionFilter::gc_distance(double lat1, double lon1, double lat2, double lon2) -{ - return radtometers(gcdist( - RAD(lat1), - RAD(lon1), - RAD(lat2), - RAD(lon2) - )); -} - /* tear through a waypoint queue, processing points by distance */ -void PositionFilter::position_runqueue(WaypointList* waypt_list, int qtype) +void PositionFilter::position_runqueue(const WaypointList& waypt_list, int qtype) { - QList qlist; - - for (auto* const waypointp : qAsConst(*waypt_list)) { - qlist.append(WptRecord(waypointp)); - } - int nelems = qlist.size(); - - for (int i = 0 ; i < nelems ; ++i) { - if (!qlist.at(i).deleted) { - bool something_deleted = false; - - for (int j = i + 1 ; j < nelems ; ++j) { - if (!qlist.at(j).deleted) { - double dist = gc_distance(qlist.at(j).wpt->latitude, - qlist.at(j).wpt->longitude, - qlist.at(i).wpt->latitude, - qlist.at(i).wpt->longitude); - - if (dist <= pos_dist) { - if (check_time) { - qint64 diff_time = std::abs(qlist.at(j).wpt->creation_time.msecsTo(qlist.at(i).wpt->creation_time)); - if (diff_time >= max_diff_time) { - continue; + if (!waypt_list.empty()) { + QList qlist; + + for (auto* const waypointp : waypt_list) { + waypointp->extra_data = nullptr; + qlist.append(WptRecord(waypointp)); + } + int nelems = qlist.size(); + + for (int i = 0 ; i < nelems ; ++i) { + if (!qlist.at(i).deleted) { + bool something_deleted = false; + + for (int j = i + 1 ; j < nelems ; ++j) { + if (!qlist.at(j).deleted) { + double dist = gc_distance(qlist.at(j).wpt->latitude, + qlist.at(j).wpt->longitude, + qlist.at(i).wpt->latitude, + qlist.at(i).wpt->longitude); + + if (dist <= pos_dist) { + if (check_time) { + qint64 diff_time = std::abs(qlist.at(j).wpt->creation_time.msecsTo(qlist.at(i).wpt->creation_time)); + if (diff_time >= max_diff_time) { + continue; + } + } + + qlist[j].deleted = true; + qlist.at(j).wpt->wpt_flags.marked_for_deletion = 1; + something_deleted = true; + } else { + // Unlike waypoints, routes and tracks are ordered paths. + // Don't eliminate points from the return path when the + // route or track loops back on itself. + if ((qtype == trkdata) || (qtype == rtedata)) { + break; } - } - - qlist[j].deleted = true; - switch (qtype) { - case wptdata: - waypt_del(qlist.at(j).wpt); - delete qlist.at(j).wpt; - break; - case trkdata: - track_del_wpt(cur_rte, qlist.at(j).wpt); - delete qlist.at(j).wpt; - break; - case rtedata: - route_del_wpt(cur_rte, qlist.at(j).wpt); - delete qlist.at(j).wpt; - break; - default: - break; - } - something_deleted = true; - } else { - // Unlike waypoints, routes and tracks are ordered paths. - // Don't eliminate points from the return path when the - // route or track loops back on itself. - if ((qtype == trkdata) || (qtype == rtedata)) { - break; } } } - } - - if (something_deleted && (purge_duplicates != nullptr)) { - switch (qtype) { - case wptdata: - waypt_del(qlist.at(i).wpt); - delete qlist.at(i).wpt; - break; - case trkdata: - track_del_wpt(cur_rte, qlist.at(i).wpt); - delete qlist.at(i).wpt; - break; - case rtedata: - route_del_wpt(cur_rte, qlist.at(i).wpt); - delete qlist.at(i).wpt; - break; - default: - break; + + if (something_deleted && (purge_duplicates != nullptr)) { + qlist.at(i).wpt->wpt_flags.marked_for_deletion = 1; } } } } - -} - -void PositionFilter::position_process_any_route(const route_head* rh, int type) -{ - if (!rh->rte_waypt_empty()) { - cur_rte = const_cast(rh); - position_runqueue(&cur_rte->waypoint_list, type); - cur_rte = nullptr; - } -} - -void PositionFilter::position_process_rte(const route_head* rh) -{ - position_process_any_route(rh, rtedata); -} - -void PositionFilter::position_process_trk(const route_head* rh) -{ - position_process_any_route(rh, trkdata); } void PositionFilter::process() { - RteHdFunctor position_process_rte_f(this, &PositionFilter::position_process_rte); - RteHdFunctor position_process_trk_f(this, &PositionFilter::position_process_trk); - - if (waypt_count() != 0) { - position_runqueue(global_waypoint_list, wptdata); - } - - route_disp_all(position_process_rte_f, nullptr, nullptr); - track_disp_all(position_process_trk_f, nullptr, nullptr); + position_runqueue(*global_waypoint_list, wptdata); + del_marked_wpts(); + + auto position_process_rte_lambda = [this](const route_head* rte) ->void { + position_runqueue(rte->waypoint_list, rtedata); + }; + auto rte_trl_lambda = [](const route_head* rte) -> void { + route_del_marked_wpts(const_cast(rte)); + }; + route_disp_all(position_process_rte_lambda, rte_trl_lambda, nullptr); + + auto position_process_trk_lambda = [this](const route_head* rte) ->void { + position_runqueue(rte->waypoint_list, trkdata); + }; + auto trk_trl_lambda = [](const route_head* rte) -> void { + track_del_marked_wpts(const_cast(rte)); + }; + track_disp_all(position_process_trk_lambda, trk_trl_lambda, nullptr); } void PositionFilter::init() { - pos_dist = 0.0; max_diff_time = 0; check_time = false; diff --git a/position.h b/position.h index 0a51d9805..8c1f8111f 100644 --- a/position.h +++ b/position.h @@ -22,12 +22,14 @@ #ifndef POSITION_H_INCLUDED_ #define POSITION_H_INCLUDED_ -#include // for QString -#include // for QVector -#include // for qint64 +#include // for QString +#include // for QVector +#include // for qint64 + +#include "defs.h" // for arglist_t, route_head (ptr only), ARG_NOMINMAX, ARGTYPE_FLOAT, ARGTYPE_REQUIRED, ARGTYPE_BOOL, Waypoint, WaypointList (ptr only) +#include "filter.h" // for Filter +#include "grtcirc.h" // for RAD, gcdist, radtometers -#include "defs.h" // for route_head (ptr only), ARG_NOMINMAX, ARGTYPE_FLOAT -#include "filter.h" // for Filter #if FILTERS_ENABLED @@ -42,7 +44,26 @@ public: void process() override; private: - route_head* cur_rte = nullptr; + /* Types */ + + class WptRecord + { + public: + explicit WptRecord(Waypoint* w) : wpt(w) {} + + Waypoint* wpt{nullptr}; + bool deleted{false}; + }; + + /* Member Functions */ + + static double gc_distance(double lat1, double lon1, double lat2, double lon2) + { + return radtometers(gcdist(RAD(lat1), RAD(lon1), RAD(lat2), RAD(lon2))); + } + void position_runqueue(const WaypointList& waypt_list, int qtype); + + /* Data Members */ double pos_dist{}; qint64 max_diff_time{}; @@ -67,21 +88,6 @@ private: }, }; - class WptRecord - { - public: - Waypoint* wpt{nullptr}; - bool deleted{false}; - - explicit WptRecord(Waypoint* w) : wpt(w) {} - }; - - static double gc_distance(double lat1, double lon1, double lat2, double lon2); - void position_runqueue(WaypointList* waypt_list, int qtype); - void position_process_any_route(const route_head* rh, int type); - void position_process_rte(const route_head* rh); - void position_process_trk(const route_head* rh); - }; #endif // FILTERS_ENABLED #endif // POSITION_H_INCLUDED_ diff --git a/radius.cc b/radius.cc index a49c5d537..ce19ceb83 100644 --- a/radius.cc +++ b/radius.cc @@ -19,40 +19,33 @@ */ +#include "radius.h" + #include // for strtod #include // for QString #include // for qAsConst, QAddConst<>::Type, foreach -#include "defs.h" // for Waypoint, waypt_del, route_add_head, route_add_wpt, route_head, waypt_add, waypt_count, xcalloc, xfree, kMilesPerKilometer -#include "radius.h" -#include "grtcirc.h" // for RAD, gcdist, radtomiles +#include "defs.h" // for Waypoint, del_marked_wpts, route_add_head, route_add_wpt, waypt_add, waypt_sort, waypt_swap, xstrtoi, route_head, WaypointList, kMilesPerKilometer #if FILTERS_ENABLED -double RadiusFilter::gc_distance(double lat1, double lon1, double lat2, double lon2) -{ - return radtomiles(gcdist(RAD(lat1), RAD(lon1), RAD(lat2), RAD(lon2))); -} - void RadiusFilter::process() { - // waypt_del may modify container. foreach (Waypoint* waypointp, *global_waypoint_list) { double dist = gc_distance(waypointp->latitude, waypointp->longitude, home_pos->latitude, home_pos->longitude); if ((dist >= pos_dist) == (exclopt == nullptr)) { - waypt_del(waypointp); - delete waypointp; - continue; + waypointp->wpt_flags.marked_for_deletion = 1; + } else { + auto* ed = new extra_data; + ed->distance = dist; + waypointp->extra_data = ed; } - - auto* ed = new extra_data; - ed->distance = dist; - waypointp->extra_data = ed; } + del_marked_wpts(); if (nosort == nullptr) { auto dist_comp_lambda = [](const Waypoint* a, const Waypoint* b)->bool { diff --git a/radius.h b/radius.h index 41945eb85..8bebd63f9 100644 --- a/radius.h +++ b/radius.h @@ -22,10 +22,12 @@ #ifndef RADIUS_H_INCLUDED_ #define RADIUS_H_INCLUDED_ -#include // for QVector +#include // for QString +#include // for QVector -#include "defs.h" // for ARG_NOMINMAX, ARGTYPE_FLOAT, ARGTYPE_REQUIRED -#include "filter.h" // for Filter +#include "defs.h" // for arglist_t, ARG_NOMINMAX, ARGTYPE_FLOAT, ARGTYPE_REQUIRED, ARGTYPE_BOOL, ARGTYPE_INT, ARGTYPE_STRING, Waypoint +#include "filter.h" // for Filter +#include "grtcirc.h" // for RAD, gcdist, radtomiles #if FILTERS_ENABLED @@ -41,6 +43,21 @@ public: void deinit() override; private: + /* Types */ + + struct extra_data { + double distance; + }; + + /* Member Functions */ + + static double gc_distance(double lat1, double lon1, double lat2, double lon2) + { + return radtomiles(gcdist(RAD(lat1), RAD(lon1), RAD(lat2), RAD(lon2))); + } + + /* Data Members */ + double pos_dist{}; char* distopt = nullptr; char* latopt = nullptr; @@ -53,10 +70,6 @@ private: Waypoint* home_pos{}; - struct extra_data { - double distance; - }; - QVector args = { { "lat", &latopt, "Latitude for center point (D.DDDDD)", @@ -88,8 +101,6 @@ private: }, }; - static double gc_distance(double lat1, double lon1, double lat2, double lon2); - }; #endif // FILTERS_ENABLED #endif // RADIUS_H_INCLUDED_ diff --git a/route.cc b/route.cc index 481987226..a83e9dd88 100644 --- a/route.cc +++ b/route.cc @@ -143,6 +143,18 @@ track_del_wpt(route_head* rte, Waypoint* wpt) global_track_list->del_wpt(rte, wpt); } +void +route_del_marked_wpts(route_head* rte) +{ + global_route_list->del_marked_wpts(rte); +} + +void +track_del_marked_wpts(route_head* rte) +{ + global_track_list->del_marked_wpts(rte); +} + void route_swap_wpts(route_head* rte, WaypointList& other) { @@ -446,6 +458,31 @@ RouteList::del_wpt(route_head* rte, Waypoint* wpt) --waypt_ct; } +void +RouteList::del_marked_wpts(route_head* rte) +{ + // For lineary complexity build a new list from the points we keep. + WaypointList oldlist; + swap_wpts(rte, oldlist); + + // mimic trkseg handling from WaypointList::del_rte_waypt + bool inherit_new_trkseg = false; + for (Waypoint* wpt : qAsConst(oldlist)) { + if (wpt->wpt_flags.marked_for_deletion) { + if (wpt->wpt_flags.new_trkseg) { + inherit_new_trkseg = true; + } + delete wpt; + } else { + if (inherit_new_trkseg) { + wpt->wpt_flags.new_trkseg = 1; + inherit_new_trkseg = false; + } + add_wpt(rte, wpt, false, u"RPT", 3); + } + } +} + void RouteList::common_disp_session(const session_t* se, route_hdr rh, route_trl rt, waypt_cb wc) { diff --git a/smplrout.cc b/smplrout.cc index 11bc30aa0..67187c638 100644 --- a/smplrout.cc +++ b/smplrout.cc @@ -139,7 +139,7 @@ double SimplifyRouteFilter::compute_track_error(const neighborhood& nb) const return track_error; } -void SimplifyRouteFilter::routesimple_tail(const route_head* rte) +void SimplifyRouteFilter::routesimple_head(const route_head* rte) { /* short-circuit if we already have fewer than the max points */ if ((limit_basis == limit_basis_t::count) && count >= rte->rte_waypt_ct()) { @@ -206,7 +206,7 @@ void SimplifyRouteFilter::routesimple_tail(const route_head* rte) /* remove the record with the lowest XTE */ neighborhood goner = errormap.last(); - goner.wpt->extra_data = &delete_flag; // mark for deletion + goner.wpt->wpt_flags.marked_for_deletion = 1; // errormap.remove(lastKey()); // with Qt 5.12.12, 5.15.2 results in asan heap-use-after-free errors in build_extra_tests.sh errormap.erase(--errormap.end()); // in Qt6 can use cend(). // wpthash.remove(goner.wpt); // removal not necessary @@ -249,41 +249,23 @@ void SimplifyRouteFilter::routesimple_tail(const route_head* rte) } } /* end of too many records loop */ - - /* delete marked points */ - // For lineary complexity build a new list from the points we keep. - WaypointList oldlist; - (*route_swap_wpts_fnp)(const_cast(rte), oldlist); - - // mimic trkseg handling from WaypointList::del_rte_waypt - bool inherit_new_trkseg = false; - for (Waypoint* wpt : qAsConst(oldlist)) { - if (wpt->extra_data == nullptr) { - if (inherit_new_trkseg) { - wpt->wpt_flags.new_trkseg = 1; - inherit_new_trkseg = false; - } - (*route_add_wpt_fnp)(const_cast(rte), wpt, u"RPT", 3); - } else { - if (wpt->wpt_flags.new_trkseg) { - inherit_new_trkseg = true; - } - delete wpt; - } - } } void SimplifyRouteFilter::process() { - RteHdFunctor routesimple_tail_f(this, &SimplifyRouteFilter::routesimple_tail); - - route_add_wpt_fnp = route_add_wpt; - route_swap_wpts_fnp = route_swap_wpts; - route_disp_all(nullptr, routesimple_tail_f, nullptr); - - route_add_wpt_fnp = track_add_wpt; - route_swap_wpts_fnp = track_swap_wpts; - track_disp_all(nullptr, routesimple_tail_f, nullptr); + auto common_head_lambda = [this](const route_head* rte)->void { + routesimple_head(rte); + }; + + auto route_tail_lambda = [](const route_head* rte)->void { + route_del_marked_wpts(const_cast(rte)); + }; + route_disp_all(common_head_lambda, route_tail_lambda, nullptr); + + auto track_tail_lambda = [](const route_head* rte)->void { + track_del_marked_wpts(const_cast(rte)); + }; + track_disp_all(common_head_lambda, track_tail_lambda, nullptr); } void SimplifyRouteFilter::init() diff --git a/smplrout.h b/smplrout.h index 7c8e0ed7c..c8d46ef2f 100644 --- a/smplrout.h +++ b/smplrout.h @@ -109,7 +109,7 @@ private: /* Member Functions */ double compute_track_error(const neighborhood& nb) const; - void routesimple_tail(const route_head* rte); + void routesimple_head(const route_head* rte); /* Data Members */ @@ -117,15 +117,12 @@ private: double error = 0; limit_basis_t limit_basis{limit_basis_t::error}; metric_t metric{metric_t::crosstrack}; - int delete_flag{}; // &delete_flag != nullptr char* countopt = nullptr; char* erroropt = nullptr; char* xteopt = nullptr; char* lenopt = nullptr; char* relopt = nullptr; - void (*route_add_wpt_fnp)(route_head* rte, Waypoint* wpt, QStringView namepart, int number_digits) {}; - void (*route_swap_wpts_fnp)(route_head* rte, WaypointList& other) {}; QVector args = { { diff --git a/waypt.cc b/waypt.cc index c2c614c35..f2bce6128 100644 --- a/waypt.cc +++ b/waypt.cc @@ -88,6 +88,12 @@ waypt_del(Waypoint* wpt) global_waypoint_list->waypt_del(wpt); } +void +del_marked_wpts() +{ + global_waypoint_list->del_marked_wpts(); +} + unsigned int waypt_count() { @@ -660,6 +666,22 @@ WaypointList::waypt_del(Waypoint* wpt) removeAt(idx); } +void +WaypointList::del_marked_wpts() +{ + // For lineary complexity build a new list from the points we keep. + WaypointList oldlist; + swap(oldlist); + + for (Waypoint* wpt : qAsConst(oldlist)) { + if (wpt->wpt_flags.marked_for_deletion) { + delete wpt; + } else { + waypt_add(wpt); + } + } +} + void WaypointList::del_rte_waypt(Waypoint* wpt) { -- 2.30.2